package com.hkb.josephusproblemlib;

/**
 * 有M个人，其编号分别为1－M。这M个人按顺序排成一个圈。
 * 现在给定一个数N，从第一个人开始依次报数，数到N的人出列，
 * 然后又从下一个人开始又从1开始依次报数，
 * 数到N的人又出列．．．如此循环，直到最后所有人出列为止。
 * 输出出列轨迹。
 *
 * @authorwayfoon
 */

public class Remove {
    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {

        //头节点单列出来，方便形成循环链表
        Node firstNode = new Node(1);
        Node x = firstNode;

        //建立单向链表
        for (int i = 2; i <= 10; i++) {
            x = (x.next = new Node(i));
        }
        //删除倒数第n个节点
        System.out.println("----------------------删除倒数第n个节点-----------------------");
        printLinkTable(firstNode);
        System.out.println();
        firstNode = remove(firstNode, 3);
        printLinkTable(firstNode);
        System.out.println();
        System.out.println("----------------------删除倒数第n个节点-----------------------");

    }

    /**
     * 删除倒数第n个节点
     *
     * @param head 头入口
     * @return
     */
    public static Node remove(Node head, int n) {
        if (head == null || n <= 0) {
            return null;
        }

        Node p = head;
        Node q = head;

        int i = 0;
        //快指针先走N个节点
        while (i < n) {
            p = p.next;

            if (p == null) {
                head = head.next;
                return head;
            }

            i++;
        }
        //快慢指针一起走,当快指针走到结尾,慢指针所在位置就是的N个节点
        while (p.next != null) {
            p = p.next;
            q = q.next;
        }
        //删除这个节点
        q.next = q.next.next;
        return head;
    }

    /**
     * 打印链表
     **/
    private static void printLinkTable(Node head) {
        Node node = head;
        while (node != null) {
            System.out.print(node.data);
            System.out.print("-");
            node = node.next;
        }
    }
}
